%%% ------------------------------------------------------------------
%%% Licensed under the Apache License, Version 2.0 (the 'License');
%%%  you may not use this file except in compliance with the License.
%%%  You may obtain a copy of the License at
%%%
%%%      http://www.apache.org/licenses/LICENSE-2.0
%%%
%%% Copyright (c) 2018 dwg <bypf2009@vip.qq.com>
%%%
%%%  Unless required by applicable law or agreed to in writing, software
%%%  distributed under the License is distributed on an 'AS IS' BASIS,
%%%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%%  See the License for the specific language governing permissions and
%%%  limitations under the License.
%%%
%%% @doc 列表做排行榜，排序、插入数据，数据内容是元组
%%% @author  dwg <'bypf2009@vip.qq.com'>
%%% @copyright 2018 dwg <bypf2009@vip.qq.com>
%%% @end
%%% created|changed : 2018-01-12 18:03
%%% coding : utf-8
%%% ------------------------------------------------------------------
-module(charts).
-author("dwg").

-behaviour(gen_server).
-export([
    start_link/0
]).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2, terminate/2, code_change/3]).
-export([
    single_insert/1,
    gap_insert/1,
    minit/4,
    u_random/3,
    msort_k3/2,
    minsert/3,
    multi_insert/2,
    multi_insert/3,
    multi_insert_merge/2,
    find/3,
    minsert_2/3
]).

-record (t, {
    k1 :: non_neg_integer(),
    k2 :: non_neg_integer(),
    k3 :: non_neg_integer(),
    v  :: any()
}).

-define (INIT_NUM, 1000).
-define (TIME, os:system_time(1000000)).

% -record(msort, {
%     index  :: list(), % indexs of the charts, increse by page size
%     charts :: list(), % chart pages
%     chart  :: list(), % all-in-one chart
%     wait   :: list(), % waiting to insert to chart
%     size   :: non_neg_integer(), % page size
%     sort_time   :: non_neg_integer(), % the time of last sort
%     insert_time :: non_neg_integer()  % the time of last insert
% }).

%% ------------------------------------------------------------------
%%    api
%% ------------------------------------------------------------------

start_link() ->
    gen_server:start_link({local, ?MODULE}, ?MODULE, {}, []).

single_insert(Single) ->
    gen_server:cast(?MODULE, {insert, Single}).

gap_insert(Gap) ->
    gen_server:cast(?MODULE, {gap_insert, Gap}).

multi_insert(Multi) ->
    gen_server:cast(?MODULE, {multi_insert, Multi}).

%% ------------------------------------------------------------------
%%    private
%% ------------------------------------------------------------------

minit(C) ->
    ?MODULE:minit(2*C, C, rand:seed(), []).
minit(0, _CN, _Uni, L) -> L;
minit(C, CN, Uni, L) ->
    {K1, Uni1} = u_random(0, CN, Uni),
    {K2, Uni2} = u_random(0, CN, Uni1),
    {K3, Uni3} = u_random(0, CN, Uni2),
    V = C,
    ?MODULE:minit(C-1, CN, Uni3, [#t{k1=K1, k2=K2, k3=K3, v=V} | L]).

%%@doc random
u_random(0, E, Uni) ->
    rand:uniform_s(E, Uni);
u_random(S, E, Uni) ->
    S0 = E - S,
    rand:uniform_s(S0, Uni) + S0.

%%@doc print
print(L) ->
    {HL, _TL} = lists:split(20, L),
    io:format("~p:~p  HL:"
              "  ~p.~n",[?MODULE, ?LINE, HL]).

%% ------------------------------------------------------------------
%%    caculate
%% ------------------------------------------------------------------

%%@doc sort
msort([]) -> [];
msort(L)  ->
    % lists:sort(fun msort_k3/2, L).
    lists:sort(fun msort_all/2, L).

msort_k3(#t{k1=K11}, #t{k1=K12})
                when K11 > K12 ->
    true;
msort_k3(#t{k1=K11, k2=K21}, #t{k1=K12, k2=K22})
                when (K11 =:= K12) andalso (K21 > K22) ->
    true;
msort_k3(#t{k1=K11, k2=K21, k3=K31},
         #t{k1=K12, k2=K22, k3=K32})
                when (K11 =:= K12) andalso (K21 =:= K22) ->
    K31 > K32;
msort_k3(_, _) ->
    false.


msort_all(#t{k1=K11, k2=K21, k3=K31},
          #t{k1=K12, k2=K22, k3=K32}) ->
    if
        %% 优先级最高
        K11 > K12 -> true;

        %% 优先级次之
        K11 =:= K12
        andalso K21 > K22 -> true;

        %% 优先级最低
        K11 =:= K12
        andalso K21 =:= K22
        andalso K31 > K32 -> true;

        %% 不考虑其它因素
        true -> false
    end.


%%@doc insert
minsert(#t{} = Test, L) ->
    ?MODULE:minsert(Test, L, []).

minsert(#t{k1=K11, k2=K21, k3=K31} = Test,
       [#t{k1=K12, k2=K22, k3=K32} = H |T], L) ->
    if
        K11 < K12 ->
            ?MODULE:minsert(Test, T, [H|L]);
        K11 > K12 ->
            ?MODULE:minsert(undefined, T, [H,Test|L]);
        K11 =:= K12 ->
            if
                K21 < K22 ->
                    ?MODULE:minsert(Test, T, [H|L]);
                K21 > K22 ->
                    ?MODULE:minsert(undefined, T, [H,Test|L]);
                K21 =:= K22 ->
                    if
                        K31 < K32 ->
                            ?MODULE:minsert(Test, T, [H|L]);
                        K31 > K32 ->
                            ?MODULE:minsert(undefined, T, [H,Test|L]);
                        K31 =:= K32 ->
                            ?MODULE:minsert(undefined, T, [Test,H|L])
                    end
            end
    end;
minsert(#t{} = Test, [], L) ->
    ?MODULE:minsert(undefined, [], [Test|L]);
minsert(undefined, [], L) ->
    lists:reverse(L);
minsert(undefined, T, L) ->
    (lists:reverse(L)) ++ T.

%%@doc multi insert,合并两个有序列表,
%%     合并两个有序列表，不管插入一个还是多个，都是遍历一次已有列表（榜单）
multi_insert(Multi, L) ->
    NewL = [],
    multi_insert(Multi, L, NewL).

multi_insert([#t{}=H | T], Tail, NewL) ->
    {Tail1, NewL1} = find(H, Tail, NewL),
    {Tail2, NewL2} = minsert_2(H, Tail1, NewL1),
    multi_insert(T, Tail2, NewL2);
multi_insert([], Tail, NewL) ->
    multi_insert_merge(Tail, NewL);
multi_insert(Multi, [], NewL) ->
    multi_insert_merge(Multi, NewL).

%%@doc merge the tail of the old chart and the the new chart
multi_insert_merge([H|T], L) ->
    multi_insert_merge(T, [H|L]);
multi_insert_merge([], L) ->
    lists:reverse(L).

%%@doc find the right place to insert the new.
find(#t{k1=K11} = Data, [#t{k1=K12}=H|T], Head) ->
    if
        K11 < K12 ->
            find(Data, T, [H|Head]);
        true ->
            find(undefined, [H|T], Head)

    end;
find(_Data, [], Head) ->
    {[], Head};
find(_, Tail, Head) ->
    {Tail, Head}.

%%@doc insert and then return the inserted-head and waiting-insert-tail
minsert_2(#t{k1=K11, k2=K21, k3=K31} = Test,
         [#t{k1=K12, k2=K22, k3=K32} = H |T], L) ->
    if
        K11 < K12 ->
            ?MODULE:minsert_2(Test, T, [H|L]);
        K11 > K12 ->
            ?MODULE:minsert_2(undefined, T, [H,Test|L]);
        K11 =:= K12 ->
            if
                K21 < K22 ->
                    ?MODULE:minsert_2(Test, T, [H|L]);
                K21 > K22 ->
                    ?MODULE:minsert_2(undefined, T, [H,Test|L]);
                K21 =:= K22 ->
                    if
                        K31 < K32 ->
                            ?MODULE:minsert_2(Test, T, [H|L]);
                        K31 > K32 ->
                            ?MODULE:minsert_2(undefined, T, [H,Test|L]);
                        K31 =:= K32 ->
                            ?MODULE:minsert_2(undefined, T, [Test,H|L])
                    end
            end
    end;
minsert_2(#t{} = Test, [], L) ->
    ?MODULE:minsert_2(undefined, [], [Test|L]);
minsert_2(undefined, T, L) ->
    {T, lists:reverse(L)}.
%% ------------------------------------------------------------------
%%    回调函数
%% ------------------------------------------------------------------

init(_Opts) ->
    %% init list
    L1 = ?MODULE:minit(?INIT_NUM),
    timer:tc(fun minit/1, [?INIT_NUM]),
    %% drop duplicate
    % Tab = ets:new(t, [public, ordered_set, named_table, {keypos, #t.k1}]),
    % ets:insert(Tab, L1),
    % L2 = ets:tab2list(Tab),
    % ets:delete(Tab),
    {ok, L1}.

handle_call(get, _From, L) ->
    {reply, L, L};

handle_call(_Request, _From, L) ->
    {reply, {error, unknown_call}, L}.

handle_cast(sort, L) ->
    timer:tc(fun msort/1, [L]),
    L1 = ?MODULE:msort(L),
    {noreply, L1};

handle_cast({insert, #t{} = Test}, L) ->
    timer:tc(fun minsert/2, [Test, L]),
    L1 = ?MODULE:minsert(Test, L),
    io:format("~p:~p Length = ~p.~n",[?MODULE, ?LINE, length(L1)]),
    {noreply, L1};

handle_cast({multi_insert, [#t{} | _T] = Multi}, L) ->
    Li1 = ?MODULE:msort(Multi),
    L1 = ?MODULE:multi_insert(Li1, L),
    timer:tc(fun multi_insert/1, [Li1, L]),
    io:format("~p:~p Length = ~p.~n",[?MODULE, ?LINE, length(L1)]),
    {noreply, L1};

handle_cast(show, L) ->
    print(L),
    {noreply, L};

handle_cast(_Unkonw, L) ->
    {noreply, L}.

handle_info(_Info, L) ->
    {noreply, L}.

terminate(_Reason, _L) ->
    ok.

code_change(_OldVsn, L, _Extra) ->
    {ok, L}.
